/*
https://leetcode-cn.com/problems/binary-tree-cameras/solution/jian-kong-er-cha-shu-by-leetcode-solution/
 */
import java.util.HashMap;
import java.util.Map;

public class Solution968 {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public int minCameraCover(TreeNode root) {
        Map<TreeNode,int[]> map=new HashMap<>();
        map.put(null,new int[]{Integer.MAX_VALUE/2,0,0});
        dfs(root,map);
        return map.get(root)[1];
    }

    private void dfs(TreeNode root, Map<TreeNode,int[]> map) {
        if (root==null){
            return;
        }
        dfs(root.left,map);
        dfs(root.right,map);
        int a=map.get(root.left)[2]+map.get(root.right)[2]+1;
        int b=Math.min(a,Math.min(map.get(root.left)[0]+map.get(root.right)[1],map.get(root.left)[1]+map.get(root.right)[0]));
        int c=Math.min(a,map.get(root.left)[1]+map.get(root.right)[1]);
        map.put(root,new int[]{a,b,c});
    }

    public static void main(String[] args) {
        System.out.println(new Solution968().minCameraCover(new TreeNode(0,new TreeNode(0,new TreeNode(0),new TreeNode(0)),null)));
    }
}
